using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEuler.Core.Helpers
{
    public class StringPerm
    {
        private readonly IList<string> _elements;
        private int Order
        {
            get { return _elements.Count; }
        }

        public StringPerm(IEnumerable<string> atoms)
        {
            _elements = atoms.ToList();
        }

        public override string ToString()
        {
            var result = new StringBuilder();
            foreach (string t in _elements)
            {
                result.Append(t);
            }
            return result.ToString();
        }
        
        private IEnumerable<string> Enumerate()
        {
            return _elements;
        }

        public IEnumerable<IEnumerable<string>> EnumerateAllPermuations()
        {
            for (var p = this; p != null; p = p.Successor())
            {
                yield return p.Enumerate();
            }
        }

        public IEnumerable<string> GetAllPermuations()
        {
            for (var p = this; p != null; p = p.Successor())
            {
                yield return p.ToString();
            }            
        }

        public StringPerm Successor()
        {
            var result = new StringPerm(_elements);

            // Step #1 - Find left value 
            int left = result.Order - 2;
            while ((result._elements[left].CompareTo(result._elements[left + 1])) >= 0 && (left >= 1))
            {
                left--;
            }
            if ((left == 0) && (_elements[left].CompareTo(_elements[left + 1])) >= 0)
            {
                return null;
            }

            // Step #2 - find right; first value > left
            int right = result.Order - 1;
            while (result._elements[left].CompareTo(result._elements[right]) >= 0)
            {
                right--;
            }

            // Step #3 - swap [left] and [right]
            string temp = result._elements[left];
            result._elements[left] = result._elements[right];
            result._elements[right] = temp;

            // Step #4 - reverse order the tail
            int i = left + 1;
            int j = result.Order - 1;
            while (i < j)
            {
                temp = result._elements[i];
                result._elements[i++] = result._elements[j];
                result._elements[j--] = temp;
            }

            return result;
        }
    }
}